1. Technical Field
This invention generally relates to data processing systems, and more specifically relates to a spin buffer and method for using the spin buffer to control accesses to semaphores in a computer system to assure data integrity of shared resources while increasing system performance.
2. Background Art
The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely sophisticated devices. However, even today's most sophisticated computer systems continue to include many of the basic elements that were present in some of the first computer systems. For example, most modern computer systems include a processor, memory, and one or more peripheral devices. In recent times, multiple processors have been introduced to enhance the computational speed of computer systems. A computer system with multiple processors typically shares memory and peripherals among the processors, rather than having separate memory and peripherals for each processor. In order to maintain the integrity of data within the computer system, a mechanism must be provided for assuring the data needed by one processor is not corrupted by another processor.
One method for assuring data integrity in computer systems with shared resources uses special signaling constructs known as semaphores. Semaphores in computer systems are typically memory locations that contain information relating to the status of shared resources. In the most common case, a separate semaphore is assigned to each shared resource. When a device (such as a processor or a peripheral) needs access to a shared resource, it first accesses the semaphore that corresponds to the shared resource to find out if the shared resource is available. If the semaphore indicates that the shared resource is available, the requesting device changes the semaphore to indicate that the shared resource is now busy, and then accesses the shared resource. This sequence is commonly known as an atomic read-modify-write cycle. When the device has completed its interaction with the shared resource, it writes data to the semaphore to indicate that the shared resource is now available for other devices to use. When a device first accesses a semaphore to determine whether the corresponding shared resource is available, if the semaphore indicates that the resource is busy (i.e., not available), the requesting device must read from the semaphore at a later time to determine whether or not the shared resource is still busy. This process of re-reading the semaphore is known as "spinning", and is typically repeated until access to the shared resource is achieved. The steps outlined above describe the theory of using semaphores to share resources in a computer system.
While the theory as described above of using semaphores is relatively simple and straightforward, the details of its implementation pose significant challenges. For example, it is possible for a first device to read from a semaphore and determine that the shared resource is available, and yet before the first device can write data to the semaphore to indicate the shared resource is no longer available, a second device could read the semaphore, which still indicates that the shared resource is available. The first device would then perform a write to the semaphore to make the shared resource unavailable, and the second device would then follow with a similar write. The result is that both the first and the second devices would believe they have exclusive access to the shared resource, which violates the integrity of the data in the shared resource and frustrates the very purpose of providing the semaphore. Thus, a method is required for locking out accesses by a device to a semaphore during the atomic read-modify-write cycle to that semaphore by another device.
One known method for resolving this problem is to block out all accesses to all semaphores until the atomic read-modify-write cycle is complete. While this approach solves the problem identified above, it does so at the expense of prohibiting all semaphore accesses until the requesting device has completed the atomic read-modify-write cycle, rather than prohibiting only accesses to the same semaphore. For the sake of simple circuit design, this brute force approach of locking out all semaphore accesses during the atomic read-modify-write cycle has become common and accepted. This approach, however, reduces system throughput by inhibiting accesses to different semaphores during the atomic read-modify-write cycle, as described below.
Referring to FIG. 1, a prior art method 100 uses semaphores to assure data integrity when multiple devices share common resources. When a device needs a shared resource (step 102), the device locks out all semaphore accesses by other devices (step 104). The device then reads the semaphore (step 106) to determine if the shared resource is available, i.e., if the shared resource is owned by another master (step 108). If the semaphore indicates that the shared resource is owned by another master, it must "spin", which means that the device must retry to gain access of the shared resource at a later time. Notice that the accesses to semaphores must be unlocked (step 110) to allow other devices to perform semaphore operations (and even to allow the device that currently owns the desired shared resource to relinquish ownership by writing to the semaphore).
If the semaphore indicates that the shared resource is not owned by another master, the device writes to the semaphore (step 112) to indicate to other devices that it owns the shared resource. Once the device has written to the semaphore (step 112), it has acquired ownership of the shared resource (step 114). The device may then unlock semaphore accesses (step 116) to allow other devices to perform semaphore accesses.
While the prior art method 100 of controlling ownership of shared resources through semaphores avoids the problem of two devices obtaining simultaneous control of a resource, it does so at the expense of locking out all semaphore accesses (step 104) until semaphore accesses are unlocked (step 116) after it has obtained ownership of the resource (step 114).
Therefore, there existed a need to selectively disable accesses to a semaphore that is currently being accessed by one bus master while allowing accesses to all other semaphores. This method of resource allocation enhances throughput by allowing different masters to access different semaphores simultaneously.